/**
 * 
 */
package backtrack.passed2;

import java.util.Arrays;

import utils.PrintUtils;

/**
 * @author xyyi
 *
 */
public class Sudoku {

	/**
	 * Valid Sudoku
	Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

	The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

	A partially filled sudoku which is valid.
	 */
    public boolean isValidSudoku1(char[][] board) {
        if (board == null || board.length < 9|| board[0].length < 9)
            return false;
        
        for (int i = 0; i < 9; i++) {
            boolean[] rowFlags = new boolean[9];
            boolean[] colFlags = new boolean[9];
            boolean[] matrixFlags = new boolean[9];
            for (int j = 0; j < 9; j++) {
                int row = i, col = j;
                int index = board[row][col] - '1';
                if (board[row][col] != '.') {
                	if (rowFlags[index])
                		return false;
                	rowFlags[index] = true;
                }
                 
                row = j; col = i;
                index = board[row][col] - '1';
                if (board[row][col] != '.') {
                	if (colFlags[index])
                		return false;
                	colFlags[index] = true;  
                }
                    
                 row = (i / 3) * 3 + j / 3;
                 col = (i % 3) * 3 + j % 3;
                 index = board[row][col] - '1';
                 if (board[row][col] != '.') {
                	 if (matrixFlags[index])
                		 return false;
                     matrixFlags[index] = true;
                 }
            }
        }
        return true;
    }
    
	public boolean isValidSudoku(char[][] board) {

		int rows = board.length;
		int cols = board[0].length;
		for (int row = 0; row < rows; row++) {
			for (int col = 0; col < cols; col++) {
				if (isValidSudoku(board, row, col) == false)
					return false;
			}
		}

		return true;
	}

	private boolean isValidSudoku(char[][] board, int row, int col) {

		if (board[row][col] == '.')
			return true;

		int length = board.length;
		boolean[] flags = new boolean[length];
		for (int i = 0; i < length; i++) {
			if (board[row][i] != '.') {
				int fi = board[row][i] - '1';
				if (!flags[fi]) {
					flags[fi] = true;
				} else {
					return false;
				}
			}
		}

		Arrays.fill(flags, false);
		for (int i = 0; i < length; i++) {
			if (board[i][col] != '.') {
				int fi = board[i][col] - '1';
				if (!flags[fi]) {
					flags[fi] = true;
				} else {
					return false;
				}
			}
		}

		Arrays.fill(flags, false);
		int rStart = row / 3 * 3;
		int cStart = col / 3 * 3;
		for (int ri = rStart, rEnd = rStart + length / 3; ri < rEnd; ri++) {
			for (int ci = cStart, cEnd = cStart + length / 3; ci < cEnd; ci++) {
				if (board[ri][ci] != '.') {
					int fi = board[ri][ci] - '1';
					if (!flags[fi]) {
						flags[fi] = true;
					} else {
						return false;
					}
				}
			}
		}
		return true;
	}

	/**
	 * Sudoku Solver
	Write a program to solve a Sudoku puzzle by filling the empty cells.

	Empty cells are indicated by the character '.'.

	You may assume that there will be only one unique solution.
	 */
	public void solveSudoku(char[][] board) {
		if (board.length != 9 || board[0].length != 9)
			return;

		solveSudokuHelp(board);
	}

	public boolean solveSudokuHelp(char[][] board) {
		int rows = board.length;
		int cols = board[0].length;
		for (int row = 0; row < rows; row++) {
			for (int col = 0; col < cols; col++) {
				if (board[row][col] == '.') {
					for (char c = '1'; c <= '9'; c++) {
						board[row][col] = c;
						if (isValidSudoku(board, row, col)
								&& solveSudokuHelp(board)) {
							return true;
						}
						board[row][col] = '.';
					}
					return false;
				}
			}
		}

		return true;
	}

    public void solveSudokuR(char[][] board) {
        if (board == null || board.length == 0)
            return;
        solveSudokuRHelp(board);
    }
    
    public boolean solveSudokuRHelp(char[][] board) {
        int rows = board.length;
        int cols = board[0].length;
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (board[row][col] == '.') {
                    for (char value = '1'; value <= '9'; value++) {
                        if (!isValid(board, row, col, value)) continue;
                        board[row][col] = value;
                        if (solveSudokuRHelp(board)) {
                        	System.out.println("XX");
                        	return true;	
                        }
                        board[row][col] = '.';
                    }
                    return false;
                }
            }
        }
        // this is only called once when the whole board is filled!
        return true;
    }
    
    private boolean isValid(char[][] board, int row, int col, char value) {
        for (int i = 0; i < 9; i++) {
            int r = row / 3 * 3 + i / 3;
            int c = col / 3 * 3 + i % 3;
            if (board[row][i] == value || board[i][col] == value || board[r][c] == value) {
                return false;   
            }
        }
        
        return true;
    }	
	
	public Sudoku() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Sudoku sudoku = new Sudoku();
//		char[][] board = { 
//				{ '.', '.', '9', '7', '4', '8', '.', '.', '.' },
//				{ '7', '.', '.', '.', '.', '.', '.', '.', '.' },
//				{ '.', '2', '.', '1', '.', '9', '.', '.', '.' },
//				{ '.', '.', '7', '.', '.', '.', '2', '4', '.' },
//				{ '.', '6', '4', '.', '1', '.', '5', '9', '.' },
//				{ '.', '9', '8', '.', '.', '.', '3', '.', '.' },
//				{ '.', '.', '.', '8', '.', '3', '.', '2', '.' },
//				{ '.', '.', '.', '.', '.', '.', '.', '.', '6' },
//				{ '.', '.', '.', '2', '7', '5', '9', '.', '.' } };
//		
//		sudoku.solveSudokuR(board);
//		PrintUtils.print2DArray(board);	
		
		char[][] board = {
			{ '.', '8', '7', '6', '5', '4', '3', '2', '1' },
			{ '2', '.', '.', '.', '.', '.', '.', '.', '.' },
			{ '3', '.', '.', '.', '.', '.', '.', '.', '.' },
			{ '4', '.', '.', '.', '.', '.', '.', '.', '.' },
			{ '5', '.', '.', '.', '.', '.', '.', '.', '.' },
			{ '6', '.', '.', '.', '.', '.', '.', '.', '.' },
			{ '7', '.', '.', '.', '.', '.', '.', '.', '.' },
			{ '8', '.', '.', '.', '.', '.', '.', '.', '.' },
			{ '9', '.', '.', '.', '.', '.', '.', '.', '.' } };		
		boolean result = sudoku.isValidSudoku1(board);
		System.out.println(result);
		
		
	}
}
